import java.util.Arrays;
import java.util.Stack;

public class leetcode695_岛屿的最大面积 {
    public static void main(String[] args) {
        Solution7 solution7 = new Solution7();
        int[][] grid = new int[][]{
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
        System.out.println(solution7.maxAreaOfIslandWithRecursion(grid));
    }
}

class Solution7 {
    public int maxAreaOfIsland(int[][] grid) {
//        Arrays.stream(grid).forEach(p -> System.out.println(Arrays.toString(p)));
        int n = grid.length, m = grid[0].length, max = 0;

        // 保证不会重复访问
        int[][] flag = new int[n][];
        for (int i = 0; i < n; i++) {
            flag[i] = new int[m];
        }
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < m; k++) {
                if (grid[i][k] == 1) {
                    int no = 1;
                    Stack<int[]> stack = new Stack<>();
                    stack.push(new int[]{i, k});
                    flag[i][k] = 1;
                    while (!stack.isEmpty()) {
                        int[] rc = stack.pop();
                        int r = rc[0], c = rc[1];
                        int[][] directions = {{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}};
                        for (int[] dir : directions) {
                            if (dir[0] >= 0 && dir[1] >= 0 && dir[0] < n && dir[1] < m && grid[dir[0]][dir[1]] == 1
                                    && flag[dir[0]][dir[1]] == 0) {
                                stack.push(dir);
                                flag[dir[0]][dir[1]] = 1;
                                no++;
                            }
                        }
                    }
                    if (no > max) {
                        max = no;
                    }
                }
            }
        }
//        Arrays.stream(flag).forEach(p -> System.out.println(Arrays.toString(p)));
        return max;
    }

// ===================================以下为递归解法===========================================//
    public int maxAreaOfIslandWithRecursion(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int k = 0; k < grid[0].length; k++) {
                max = Math.max(max, dfs(i, k, grid));
            }
        }
        return max;
    }

    private int dfs(int r, int c, int[][] grid) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[r].length || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0;
        return 1 + dfs(r - 1, c, grid) + dfs(r + 1, c, grid) + dfs(r, c - 1, grid) + dfs(r, c + 1, grid);
    }
}
